# LeetCode 76 题，Minimum Window Substring
import sys

MAX_INT = sys.maxsize
print(MAX_INT)

max_float = float('inf')
print(max_float)


# d = {}
# d['a'] = 0
# d['a'] += 1
# print('a' in d)
# print(d)


# 字典值加1
def dict_add(window, c):
    if c in window:
        window[c] += 1
    else:
        window[c] = 1


def min_window(s, t: str):
    need = {}
    window = {}
    for k in t:
        need[k] = 1
    print(need)

    left, right = 0, 0
    valid = 0
    # 记录最小字符串的起始索引及长度
    start = 0
    length = MAX_INT
    while right < len(s):
        # c是将要移入窗口的字符
        c = s[right]
        # 右移
        right += 1  # 上来就右移，行程左闭右开
        if c in need:
            dict_add(window, c)
            if window[c] == need[c]:  # 相等代表字符出现次数1，即第一次加入到window字典
                valid += 1  # 相等的时候有效数量+1

        # 判断左侧窗口是否要收缩
        while valid == len(need):
            # 在这里更新最小覆盖子串
            if right - left < length:
                start = left
                length = right - left
            # d 是将移出窗口的字符
            d = s[left]
            left += 1
            # 进行窗口内数据的一系列更新
            if d in need:
                if window[d] == need[d]:  # 在window移除之前检查，
                    valid -= 1
                window[d] -= 1

    print('start:%d length:%d' % (start, length))
    # 返回最小覆盖子串
    if length == MAX_INT:
        return ""
    else:
        return s[start: start + length]


if __name__ == '__main__':
    a = 'ADOBECODEBANC'
    b = 'ABC'
    print(min_window(a, b))
